package org.example.list;

import java.util.Iterator;

public class DoublyLinkedListSentinel implements Iterable<Integer>{

    static class Node{
        //前驱节点
        Node prev;
        //后继节点
        Node next;
        //值
        int value;
        public Node(int value,Node prev,Node next)
        {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }
    //头节点
    private Node head;
    //尾节点
    private Node tail;

    public DoublyLinkedListSentinel(){
        head = new Node(666,null,null);
        // 尾的前驱节点指向头
        tail = new Node(888,head,null);
        //头的后继节点指向尾
        head.next = tail;
    }

    /**
     * 根据索引查找节点
     * @param index 索引
     * @return 节点
     */
    private Node findNode(int index){
        //头哨兵下标为 -1 需要查询出头哨兵的索引（插入索引0时）
        int i = -1;
        for (Node p = head; p!=tail;p = p.next,i++){
          if(index == i){
              return p;
          }
        }
        return null;
    }

    public int remove(int index){
        Node removed = findNode(index);
        if (removed == null){
            throw new IllegalArgumentException(String.format("index [%d]",index));
        }
        Node prev = removed.prev;
        Node next = removed.next;

        prev.next = next;
        next.prev = prev;
        return removed.value;
    }

    public void addLast(int value){
        Node last = tail.prev;

        Node newNode = new Node(value, last, tail);

        last.next = newNode;
        tail.prev = newNode;
    }

    public int removeLast(){
        Node last = tail.prev;
        if(last==head){
            throw new IllegalArgumentException("index [0]");
        }
        Node prev = last.prev;

        prev.next = tail;
        tail.prev = prev;
        return last.value;

    }

    public void insert(int index,int value){
        // 找到插入后的前驱节点和后继节点
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new  IllegalArgumentException(String.format("index[%d]",index));
        }
        Node next = prev.next;
        // 插入节点的后继节点指向前驱节点的后继节点
        // 插入节点的前驱节点指向后继节点的前驱节点
        Node newNode = new Node(value, prev, next);
        // 前驱节点的后继指向该节点
        prev.next = newNode;
        // 后继节点的前驱指向该节点
        next.prev = newNode;

    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            //起始
            Node p = head.next;

            @Override
            public boolean hasNext() {
                return p!=tail;
            }

            @Override
            public Integer next() {
                int result = p.value;
                p = p.next;
                return result;
            }
        };
    }


    public static void main(String[] args) {
        DoublyLinkedListSentinel list = new DoublyLinkedListSentinel();


        list.addLast(1);
        list.insert(1,2);
        list.addLast(3);

        list.addLast(4);

        System.out.println("removed0======"+list.removeLast());
        for (Integer i : list) {
            System.out.println(i);
        }
        System.out.println("removed0======"+list.remove(0));
        System.out.println("removed0======"+list.remove(0));
        System.out.println("removed0======"+list.remove(0));
        //System.out.println("removed0======"+list.removeLast());

    }
}
